When configuring a product online, the user is typically presented with a number of components or features that can be selected. These selectable components or features are referred to as variables. For each variable, there are a number of choices. For example, when configuring a personal computer, the user may be asked to select components such as a processor or a disk drive. For each of these components, the user is presented with choices, such as 500 MHz, 600 MHz and 700 MHz for the processor component, and 10 Gbyte, 20 Gbyte, and 30 Gbyte for the disk drive. The set of all choices for a particular variable is referred to as the variable's domain. Each choice in the domain is called a domain member. Thus, in the example above, the processor is a variable having a domain that includes members 500 MHz, 600 MHz and 700 MHz processors. Likewise, the disk drive is a variable having a domain that includes members 10 Gbyte, 20 Gbyte, and 30 Gbyte disk drives. In general, a user can select a domain member for each variable of a configurable product thereby affording the user desirable product flexibility and a positive overall online configuration experience.
During a typical online configuration session, some domain members of one or more variables of the configurable product are not compatible with some domain members of other variables of that same product. For instance, processor speeds of 500 MHz or lower might not be compatible with 30 Gbyte disk drives (for whatever reason). In short, not all of the possible combinations of variables associated with a configurable product are valid. The validity relationships among the variables are expressed as constraints. Constraint-based configuration ensures that only valid choices will prevail in the final configured product. This is accomplished through the process of constraint propagation.
More specifically, as the user enters choices for each variable in turn, the constraints on those choices are propagated throughout the configuration problem associated with that particular configuration session. Variable domain members that are incompatible with user choices currently entered are derived from the propagated constraints, and can be displayed to the user. One way of denoting such incompatibilities is to gray out the incompatible domain members on the user's display window, or to simply remove the incompatible domain members from the user's display window. Thus, selection of the 500 MHz processor might cause the 30 Gbyte disk drive choice to be grayed out on the display, or otherwise eliminated from the available valid choices.
Bounceback Problem
In general, the bounceback problem causes domain members to be unnecessarily removed from the possible choices thereby inhibiting the configuration process. For example, assume that the 500 MHz processor is only compatible with the 10 and 20 Gbyte disk drives, that the 600 MHz processor is only compatible with the 20 Gbyte disk drive, and that the 700 MHz processor is only compatible with the 30 Gbyte disk drive. Given these constraints, selection of the 500 MHz processor causes elimination of the 30 Gbyte disk drive. This result essentially reflects the intended purpose of a configuration system and is not problematic.
However, the 700 MHz processor is only compatible with the 30 GB disk drive. As such, conventional constraint propagation causes elimination of the 700 MHz processor as well. Thus, the 700 MHz processor is also eliminated because the 500 MHz processor was chosen. Stated in terms of the bounceback problem, the 700 MHz process was grayed out by bounceback propagation of constraints caused by the selection of the 500 MHz processor. Note that if the 700 MHz processor were selected, the 500 MHz processor would effectively be deselected and no constraint violation would occur. It can be seen, therefore, that the elimination of the 700 MHz processor due to bounceback behavior inhibits the configuration process thereby adversely affecting the efficiency of a configuration system.
To exacerbate this situation, multiple constraints among several variables form a constraint network of arbitrary complexity for many real world constraint-based configuration problems. Propagation over such a network of constraints may engender bounceback behavior through propagation routes that are much more elaborate and circuitous than the given example above. As such, any one constraint-based configuration problem will generally present a unique set of bounceback behavior challenges. Thus, a bounceback behavior solution must be flexible in its implementation.
There is a need, therefore, for a configuration technique that precludes the elimination of domain members based solely on bounceback behavior. The technique should provide an efficient and flexible process that detects bounceback behavior for an arbitrary network of constraints.